public class Day11 {

    private static Day11 day11 = new Day11();
    private static int[] arr = new int[]{4,19,14,5,-3,1,8,5,11,15};
    public static void main(String[] args) {
        ListNode list = ListUnit.createList(arr);
        ListNode list2 = ListUnit.createList(new int[]{1,2,3});
//        ListNode l3 = day11.merge(list, list2);
        ListNode l3 = day11.toSortList(list, null);
        while(l3 != null) {
            System.out.println(l3.val);
            l3 = l3.next;
        }
    }
    // 方法2 --> 归并
    // tail 是不包含的
    private ListNode toSortList(ListNode head, ListNode tail) {
        if(head == tail) {
            return head;
        }
        if(head.next == tail) {
            head.next = null;// 这个可以划分出来界限，让 tail 一直为 null
            return head;
        }
        ListNode slow = head, fast = head;
        while(fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 分
        ListNode list1 = toSortList(head, slow);
        ListNode list2 = toSortList(slow, tail);

        return merge(list1, list2);
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode cur1 = list1, cur2 = list2;
        ListNode head = new ListNode(0), cur = head;
        while(cur1 != null && cur2 != null) {
            if(cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if(cur1 != null) {
            cur.next = cur1;
        } else if (cur2 != null) {
            cur.next = cur2;
        }
        return head.next;
    }
    // 选择排序 --> 时间超出

    public ListNode sortList(ListNode head) {
        if(head == null) {
            return null;
        }
        int len = getLen(head) - 1; // 得到总长度（遍历次数）
        ListNode ret = new ListNode(0);
        ListNode head2 = new ListNode(0); // 给原来的链表添加哨兵位 这样就不用判断 prev 是否为 null
        ListNode curRet = ret;
        head2.next = head;
        while(len-- != 0) {
            ListNode cur = head2.next;
            ListNode minNode = cur;// 最小的节点
            ListNode prev = head2 , prevMin = head2;
            while(cur != null) {
                if(cur.val < minNode.val) {
                    minNode = cur;
                    prevMin = prev;
                }
                System.out.println("1 cur.val" + cur.val);
                prev = cur;
                cur = cur.next;
            }
            prevMin.next = minNode.next;// 在原链表中删除该节点
            System.out.println("2 minNode.val" + minNode.val);
            curRet.next = minNode;
            curRet = curRet.next;
        }
        curRet.next = head2.next;
        head2.next = null;

        return ret.next;
    }



    private int getLen(ListNode head) {
        int len = 0;
        while(head != null) {
            len++;
            head = head.next;
        }
        return len;
    }



}
